/*
 * @lc app=leetcode.cn id=234 lang=cpp
 *
 * [234] 回文链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    /* 时间空间复杂度都不符合
    bool isPalindrome(ListNode* head) {
        vector<int> res;
        ListNode* p = head;
        while(p!=NULL)
        {
            res.push_back(p->val);
            p = p->next;
        }
        int n = res.size();
        for(int i = 0 ; i < n/2 ;i++)
        {
            if(res[i]!=res[n-i-1])
                return false;
        }
        return true;
    }*/

    // 待调试
    ListNode* successor;
    ListNode* reverseN(ListNode* head,int n)
    {
        if(n == 1)
        {
            successor = head->next ;
            return head;
        }
        ListNode* last = reverseN(head->next,n-1);
        head->next->next = head;
        head->next = successor;
        return last;

    }
    bool isPalindrome(ListNode* head) {
        if(head == NULL || head->next == NULL)
            return true;

        ListNode* slow = head;
        ListNode* fast = head;
        int count = 0;

        while(fast!=NULL && fast->next!=NULL)
        {
            slow = slow->next;
            fast = fast->next->next;
            count++;
        
        }
        ListNode* p = reverseN(head,count);
        while(slow!=NULL)
        {
            if(p->val != slow->val)
                return false;
            slow = slow->next;
            p = p->next;
        }
        return true;
    }

/*
    // 递归
    ListNode *tmp;
    bool isPalindrome(ListNode* head) {
        tmp = head;
        return check(head);
    }

    bool check(ListNode* head)
    {
        if(head==NULL)
            return true;
        bool res = check(head->next) && (tmp->val == head->val);
        tmp = tmp->next;
        return res;
    }

*/
};
// @lc code=end

